package com.fantastic.sort;

import java.util.Arrays;

/**
 * @author : fantastic
 * @date : 2024/5/15 14:34
 * @desc : this class for
 * 快速排序（Quicksort）是对冒泡排序的一种改进，
 * 借用了分治的思想，由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
 * 其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，
 * 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 * 平均时间复杂度	O(nlogn)
 * 空间复杂度 O(1)

 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {15, 20, 10, 11, 14, 9, 9, 10, 13};
//        quickSort(arr,0,arr.length-1);
        quickSort2(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 挖坑法
     *
     * @param arr
     * @param low
     * @param high
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0) {
            return;
        }
        if (low >= high) {
            return;
        }
        int left = low;
        int right = high;
        //挖坑1：保存基准的值
        int temp = arr[left];
        while (left < right) {
            //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
            while (left < right && arr[right] >= temp) {
                right--;
            }
            arr[left] = arr[right];
            //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
            while (left < right && arr[left] <= temp) {
                left++;
            }
            arr[right] = arr[left];
        }
        //基准值填补到坑3中，准备分治递归快排
        arr[left] = temp;
        System.out.println("Sorting: " + Arrays.toString(arr));
        quickSort(arr, low, left - 1);
        quickSort(arr, left + 1, high);
    }

    /**
     * 左右指针法
     *
     * @param arr
     * @param low
     * @param high
     */
    public static void quickSort2(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;
        int temp = arr[low];

        while (left < right) {
            //从右向左查找比基准小的数
            while (left < right && arr[right] >= temp) {
                right--;
            }
            //从左向右查找比基准大的数
            while (left < right && arr[left] <= temp) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        swap(arr, low, left);

        quickSort2(arr, low, left - 1);
        quickSort2(arr, left + 1, high);
    }

    public static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}
